//
// Created by 紫霄 on 2020/4/8.
//

#ifndef LEETCODE_07_REBUILDBINTREE_H
#define LEETCODE_07_REBUILDBINTREE_H
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <iterator>
#include <vector>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
  TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    if (!preorder.empty()) {
      if (preorder.size() == 1) {
        TreeNode *n = new TreeNode(preorder[0]);
        return n;
      } else {
        //// 这里使用new；如果不使用new 直接生成，然后使用，会报错；
        TreeNode *a = new TreeNode(preorder[0]);
        int c = 0;
        for (int i = 0; i < inorder.size(); ++i) {
          if (inorder[i] == preorder[0]) {
            c = i;
            break;
          }
        }
        vector<int> leftPre = {};
        vector<int> leftIn = {};
        vector<int> rightPre = {};
        vector<int> rightIn = {};
        for (int i = 0; i < c; ++i) {
          leftPre.push_back(preorder[i + 1]);
          leftIn.push_back(inorder[i]);
        }
        for (int i = c + 1; i < preorder.size(); ++i) {
          rightPre.push_back(preorder[i]);
          rightIn.push_back(inorder[i]);
        }
        a->left = buildTree(leftPre, leftIn);
        a->right = buildTree(rightPre, rightIn);
        return a;
      }
    } else {
      return NULL;
    }
  }
};

#endif // LEETCODE_07_REBUILDBINTREE_H
